package listbyorder.access101_200.test113;

import listbyorder.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/7 11:54
 */
public class Solution2 {

    // 方法二 ： DFS求解，走到底下再回来
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> temp = new ArrayList<>();
        TreeNode cur = root;
        TreeNode pre = null;
        int curSum = 0;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                curSum += cur.val;
                temp.add(cur.val);
                cur = cur.left;
            }
            cur = stack.peek();
            if (curSum == sum && cur.left == null && cur.right == null) {
                // 表示到达了根节点
                res.add(new ArrayList<>(temp));
            }
            // 当走到最低下的时候，分为两种情况
            if (cur.right == null || cur.right == pre) {
                // 一个是当cur节点是叶子节点的时候， 另一种情况是当前cur节点的叶子节点我们以及访问过
                // 那么这个时候发生操作其实就是回溯
                TreeNode pop = stack.pop();
                curSum -= pop.val;
                temp.remove(temp.size() - 1);
                pre = cur;
                cur = null;
            } else {
                // 此节点不是叶子节点
                cur = cur.right;
            }
        }
        return res;
    }
}
